[54, 226, 93, 17, 77, 31, 44, 55, 20]  # 升序排序

[54, 226, 93, 17, 77, 31, 44, 55, 20]
[54, 93, 226, 17, 77, 31, 44, 55, 20]
[54, 93, 17, 226, 77, 31, 44, 55, 20]
[54, 17, 93, 226, 77, 31, 44, 55, 20]
[17, 54, 93, 226, 77, 31, 44, 55, 20]
[17, 54, 93, 77, 226, 31, 44, 55, 20]
[17, 54, 77, 93, 226, 31, 44, 55, 20]

# .....
[17, 31, 44, 54, 55, 77, 93, 226, 15]
# 最坏时间复杂度  n*n=O(n^2)
# 最优时间复杂度  n*1=O(n)
[17, 20, 31, 44, 54, 55, 77, 93, 226, 1000]

# 稳定性 :稳定的
[17, 20, 31, 44, 54, 55, 77, 93, 77, 226]
[17, 20, 31, 44, 54, 55, 77, 77, 93, 226]


# 插入排序
def insert_sort(alist):
    n = len(alist)
    for j in range(1, n):  # n-1   n
        i = j
        while i > 0:  # 和有序列表中每个元素进行比较 （从最后一个开始）
            if alist[i] < alist[i - 1]:  # 如果当前元素比前一个元素小，则进行交换
                alist[i], alist[i - 1], = alist[i - 1], alist[i]
            else:  # 否则已经是有序列表，不需要交换了，则退出循环
                break
            i -= 1


if __name__ == '__main__':
    alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
    print('原数组：', alist)
    insert_sort(alist)
    print('排序后：', alist)
